package Hot100.BackTracking;

import java.util.ArrayList;
import java.util.List;

public class letterCombinations {
    public static void main(String[] args) {
        String digits = "23";
        System.out.println(new letterCombinations().letterCombinations(digits));
    }
    List<String> result = new ArrayList<>();
    String path = "";
    String[] letterMap = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return result;
        }
        backTrack(digits,0);
        return result;
    }
    public void backTrack(String digits,int index){
        if(index == digits.length()){
            result.add(path);
            return;
        }
        int digit = (digits.charAt(index) - '0');
        String letters = letterMap[digit];
        for (int i = 0; i < letters.length(); i++) {
            path += letters.charAt(i);
            backTrack(digits,index + 1);
            path = path.substring(0, path.length() - 1);
        }
    }
}
